题解 P2403 【[SDOI2010]所驼门王的宝藏】

发表于 | 更新于

题面

$Tarjan+toposort$的经典套路题吧，$Tarjan+toposort$应该一眼就能看出来，但是发现对于第$1$,$2$种边连边显然会超时，这里用了一种比较无脑简单的方法(像我这种小蒟蒻都能想出来肯定简单啊)，这里以第$1$种为例(第二种类比一下就可以了)

若有多个第一种门在某一行，那么这些门都是可以互相到达的，但是我们两两之间连$n^2$的边显然很愚蠢，只需要连成一个环即可(第$1$个连第$2$个，第$2$个连第$3$个，最后一个连第$1$个)，在这个环上的其他所有点，只需从环上任意一点连出去即可(像对于网络流时经常用的建一个虚点连接两边优化$n^2$连边的方法应该也可以)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 1003000
#define mod 19260817
#define pb push_back
using namespace std;
struct node1{
    int u,to,next;
}e[N<<4];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
unordered_map<ll,int>mp,ed;
vector<int>x[N],y[N];
int dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1};
int opt[N],R,C,m,u[N],v[N],cnt=1,head[N],dfn[N],low[N],ans,f[N],st[N],top,num,col,in[N],w[N],color[N];
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].u=u;
    e[cnt].next=head[u];
    head[u]=cnt;
}
inline ll h(ll x,ll y){
    return 1ll*(x-1)*C+1ll*y;
}
inline ll ee(ll x,ll y){
    return 1ll*(x-1)*col+1ll*y;
}
void Tarjan(int u){
    dfn[u]=low[u]=++num;
    st[++top]=u;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if (!color[v])
            low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u]){
        ++col;
        do{
            ++w[col];color[st[top--]]=col;
        }while (st[top+1]!=u);
    }
}
void topo(){
    queue<int>q;
    for (int i=1;i<=col;++i)if (!in[i])q.push(i),f[i]=w[i];
    while (!q.empty()){
        int u=q.front();q.pop();
        for (int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            --in[v];
            f[v]=max(f[v],f[u]+w[v]);
            if (!in[v])q.push(v);
        }
    }
}
signed main(){
    m=read(),R=read(),C=read();
    for (int i=1;i<=m;++i){
        u[i]=read(),v[i]=read(),opt[i]=read();
        mp[h(u[i],v[i])]=i;
        x[u[i]].pb(i);
        y[v[i]].pb(i);
    }
    for (int i=1;i<=R;++i){
        int st=0,cnt=0;
        while (st<x[i].size()&&opt[x[i][st]]!=1)++st;int last;
        if (st!=x[i].size()){++cnt;last=x[i][st];}
        if (cnt)for (int j=0;j<st;++j)add(last,x[i][j]);
        for (int j=st+1;j<x[i].size();++j)
            if (opt[x[i][j]]==1){
                add(last,x[i][j]);
                last=x[i][j];++cnt;
            }else add(x[i][st],x[i][j]);
        if (cnt>1)add(last,x[i][st]);
    }
    for (int i=1;i<=C;++i){
        int st=0,cnt=0;
        while (st<y[i].size()&&opt[y[i][st]]!=2)++st;int last;
        if (st!=y[i].size()){++cnt;last=y[i][st];}
        if (cnt)for (int j=0;j<st;++j)add(last,y[i][j]);
        for (int j=st+1;j<y[i].size();++j)
            if (opt[y[i][j]]==2){
                add(last,y[i][j]);
                last=y[i][j];++cnt;
            }else{add(y[i][st],y[i][j]);}
        if (cnt>1)add(last,y[i][st]);
    }
    for (int i=1;i<=m;++i)
        if (opt[i]==3)
            for (int ii=0;ii<8;++ii){
                int x=u[i]+dx[ii],y=v[i]+dy[ii];
                if (!mp[h(x,y)])continue;
                add(i,mp[h(x,y)]);
            }
    for (int i=1;i<=m;++i)
        if (!dfn[i])
            Tarjan(i);
    int tot=cnt;memset(head,0,sizeof(head));cnt=0;
    for (int i=1;i<=tot;++i){
        int u=e[i].u,v=e[i].to;
        if (color[u]!=color[v]){
            if (ed[ee(color[u],color[v])])continue;
            add(color[u],color[v]);
            ed[ee(color[u],color[v])]=1;
            ++in[color[v]];
        }
    }
    topo();
    for (int i=1;i<=col;++i)
        ans=max(ans,f[i]);
    cout<<ans;
    return 0;
}